\documentclass[submission]{FPSAC2017}

\articlenumber{64}
\addbibresource{64_Bagno_Adin_Roichman.bib}

\usepackage[enableskew,vcentermath]{youngtab}
\usepackage{ytableau}

\usepackage{tikz, hyperref,MnSymbol}
\usepackage{amsfonts}
\usepackage[enableskew,vcentermath]{youngtab}
\usepackage{tikz-cd}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{formula}[theorem]{Formula}
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{cla}[theorem]{Claim}
\newtheorem{con}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prb}[theorem]{Problem}
\newtheorem{que}[theorem]{Question}
\theoremstyle{definition}
\newtheorem{obs}[theorem]{Observation}
\newtheorem{pres}[theorem]{Presentation}
\newtheorem{fac}[theorem]{Fact}
\newtheorem{exa}[theorem]{Example}
\newtheorem{example}[theorem]{Example}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{df}[theorem]{Definition}
\newtheorem{alg}[theorem]{Algorithm}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{problem}[theorem]{Problem}



\usepackage{lipsum}
\newcommand{\bbn}{\mathbb{N}}
\newcommand{\bbz}{\mathbb{Z}}
\newcommand{\bbq}{\mathbb{Q}}
\newcommand{\bbr}{\mathbb{R}}
\newcommand{\bbs}{\mathbb{S}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\bft}{\mathbf{t}}
\newcommand{\bpi}{\bar{\pi}}
\newcommand{\then}{\Longrightarrow}
\newcommand\x{{\mathbf x}}
\DeclareMathOperator\sign{sign}
\DeclareMathOperator\Des{Des}
\DeclareMathOperator\des{des}
\DeclareMathOperator\ldes{ldes}
\DeclareMathOperator\stat{stat}
\DeclareMathOperator\inv{inv}
\DeclareMathOperator\SYT{SYT}
\DeclareMathOperator\vdes{vdes}
\DeclareMathOperator\maj{maj}
\DeclareMathOperator\bl{bl}
\DeclareMathOperator\nb{nb}

\DeclareMathOperator\Ltr{ltrMax}

\DeclareMathOperator\cDes{cDes}
\newcommand\uu{\mathbf{u}}
\newcommand\vv{\mathbf{v}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\enc}{\nu}
\renewcommand\S{{\mathcal S}}
\newcommand{\forsingle}{\diagup}
\newcommand{\fordouble}{\diagup}
\newcommand{\backsingle}{\diagdown}
\newcommand{\backdouble}{\diagdown}
\newcommand{\vertsingle}{\vert}
\newcommand{\vertdouble}{\vert}
\newcommand{\horsingle}{-}
\newcommand{\hordouble}{-}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\sphere}{\mathbb{S}}

\newcommand{\BBB}{{\mathcal{B}}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\ch}{\operatorname{ch}}
\newcommand{\deleted}[1]{ }
\newcommand{\Q}{{\mathcal Q}}

\DeclareMathOperator\ides{ides} \DeclareMathOperator\imaj{imaj}

\title[Block numbers of permutations and Schur-positivity]{Block numbers of permutations and Schur-positivity}


\author{Ron M.\ Adin\addressmark{1}%
\thanks{\href{mailto:radin@math.biu.ac.il}{radin@math.biu.ac.il}},
Eli Bagno\addressmark{2}\thanks{\href{mailto:bagnoe@jct.ac.il}{bagnoe@jct.ac.il}}
\and Yuval Roichman\addressmark{1}%
\thanks{\href{mailto:yuvalr@math.biu.ac.il}{yuvalr@math.biu.ac.il}}
}

\address{\addressmark{1}Department of Mathematics, Bar-Ilan University, Ramat-Gan, Israel \\ \addressmark{2}Department of Applied Mathematics, Jerusalem College of Technology, Jerusalem, Israel}


\received{November 14, 2016}

\abstract{
The {\em block number} of a permutation is the maximal number of components in its expression as a direct sum.
We show that the distribution of the set of left-to-right-maxima over $321$-avoiding permutations with a given block number $k$ 
is equal to the distribution of this set over $321$-avoiding permutations with the last descent of the inverse permutation at position $n-k$.
This result is analogous to the Foata-Sch\"{u}tzenberger equi-distribution theorem,
and implies Schur-positivity of the quasi-symmetric generating function of descent set over $321$-avoiding permutations with a prescribed block number.}

\keywords{Schur positivity, permutation statistics, pattern
avoidance, quasi-symmetric function.}


\begin{document}

\maketitle


\section{Introduction}

Given any subset $A$ of the symmetric group $\S_n$, define the
quasi-symmetric function
\[
\Q(A) := \sum\limits_{\pi\in A} \F_{n,\Des(\pi)},
\]
where $\Des(\pi):=\{i:\ \pi(i)>\pi(i+1)\}$ is the {\em descent
set} of $\pi$ and $\F_{n,D}$ (for $D \subseteq [n-1]$) are
Gessel's {\em fundamental quasi-symmetric functions;} see
\cref{sec:prel_quasi} for more details. The following
long-standing problem was first posed in~\cite{Gessel-Reutenauer}.

\begin{problem}\label{prob:symmetric}
For which subsets $A\subseteq \S_n$ is $\Q(A)$ symmetric?
\end{problem}

A symmetric function is {\em Schur-positive} if all the
coefficients in its expansion in the basis of Schur functions are
nonnegative. Determining whether a given symmetric function is
Schur-positive is a major problem in contemporary algebraic
combinatorics~\cite{Stanley_problems}.

Call a subset $A \subseteq \S_n$ {\em Schur-positive} if $\Q(A)$
is symmetric and Schur-positive. Classical examples of
Schur-positive sets of permutations include inverse descent
classes~\cite{Gessel}, Knuth classes~\cite{Gessel}, conjugacy
classes~\cite[Theorem 5.5]{Gessel-Reutenauer}, and permutations with a
fixed inversion number~\cite[Prop. 9.5]{Adin-R}.


New constructions of Schur-positive sets of permutations were
described in~\cite{ER} and ~\cite{Sagan_talk}. Inspired by these
examples, Sagan and Woo raised the problem of finding
Schur-positive pattern-avoiding sets~\cite{Sagan_talk}.


The goal of this paper is to present a new example of a
Schur-positive set of permutations which involves
pattern-avoidance: the set of $321$-avoiding permutations having a
prescribed number of blocks.
We shall state that more explicitly.

A permutation $\pi \in \S_n$ is {\em $321$-avoiding} if the sequence
$(\pi(1), \ldots, \pi(n))$ contains no decreasing subsequence of length $3$.  
Denote by $\S_n(321)$ the set of $321$-avoiding permutations in $\S_n$. 
For a permutation $\pi \in \S_n$ let
\[
\bl(\pi) := |\{ i \,:\, (\forall j \le i)\, \pi(j) \le i \}|
\]
be the {\em block number} of $\pi$.
The block number was studied in~\cite{St3} and references therein,
as the cardinality of the {\em connectivity set} of $\pi$. 
Denote
\[
Bl_{n,k} := \{\pi\in \S_n(321) \,:\, \bl(\pi) = k\}.
\]

Recall the {\em Frobenius characteristic map} $\ch$, 
from class functions on $\S_n$ to symmetric functions, 
defined by $\ch(\chi^{\lambda}) = s_{\lambda}$ and extended by linearity. Our
main result is:

\begin{theorem}\label{conj1}
For any $1\le k\le n$,
the set $Bl_{n,k}$
is Schur-positive.
In fact, for $1 \le k \le n-1$
\[
\Q(Bl_{n,k}) = \ch(\chi^{(n-1,n-k)}
\downarrow_{\S_n}^{\S_{2n-k-1}}),
\] 
where $\chi \downarrow ^G_H$ stands for the restriction of the character $\chi$ from the group $G$ to the group $H$;
and, for $k = n$
\[
\Q(Bl_{n,n}) = \ch(\chi^{(n)}) = s_{(n)}.
\]
\end{theorem}

The coefficients of the Schur expansion of $\Q(Bl_{n,k})$
are described in Equation~\eqref{eq_coeff} below.


The proof of \cref{conj1} involves a left-to-right-maxima-pre\-serving bijection
and a resulting equi-distribution result.
Specifically, let
\[
\Ltr (\pi) := \{i \,:\, \pi(i) = \max\{\pi(1), \ldots, \pi(i)\}\}
\]
be the set of {\em left-to-right maxima} in a permutation $\pi$. 
The {\em descent set} of 
$\pi$ is
\[
\Des(\pi) := \{i \,:\, \pi(i)>\pi(i+1)\}.
\]
Define
\[
\ldes(\pi) := \max\{i \,:\, i \in \Des(\pi)\}
\]
to be the {\em last descent} of $\pi$, with $\ldes(\pi) := 0$ if
$\Des(\pi) = \varnothing$ (i.e., if $\pi$ is the identity
permutation).  

For every $I \subseteq [n]$, let ${\bf x}^I:=\prod_{i \in I} x_i$.  Our equi-distribution result is:

\begin{theorem}\label{main1_introduction}
For every positive integer $n$
\[
\sum_{\pi\in \S_n(321)}  {\bf x}^{\Ltr(\pi)} q^{\bl(\pi)} =
\sum_{\pi\in \S_n(321)}  {\bf x}^{\Ltr(\pi)}
q^{n-\ldes(\pi^{-1})}.
\]
\end{theorem}

See also \cref{t:des_equid} below.

\begin{remark}
An equivalent formulation, replacing $\pi$ by $\pi^{-1}$ and using
$\bl(\pi^{-1}) = \bl(\pi)$, is:
\[
\sum_{\pi\in \S_n(321)}  {\bf x}^{\Ltr(\pi^{-1})} q^{\bl(\pi)} =
\sum_{\pi\in \S_n(321)}  {\bf x}^{\Ltr(\pi^{-1})}
q^{n-\ldes(\pi)}.
\]
It is reminiscent of the classical Foata-Sch\"{u}tzenberger
Theorem
\[
\sum_{\pi\in \S_n}  {\bf x}^{\Des(\pi^{-1})} q^{\inv(\pi)} =
\sum_{\pi\in \S_n}  {\bf x}^{\Des(\pi^{-1})} q^{\maj(\pi)};
\]
see \cref{obs2} below.
\end{remark}

After some necessary preliminaries in \cref{sec:prelim},
we shall state a basic enumerative result in \cref{sec:block_number}.
Then \cref{sec:equidistribution} will outline the main idea in the proof of \cref{main1_introduction}, and \cref{sec:Schur} will deduce \cref{conj1} from a corollary of \cref{main1_introduction}.
\cref{sec:final_remarks} contains some final remarks.


\section{Preliminaries}\label{sec:prelim}


\subsection{Statistics on permutations and on SYT}\label{subsec:stat}

For a positive integer $n$ let $[n]:=\{1,2,\dots,n\}$, and let
$\S_n$ denote the $n$-th symmetric group, the group of all
permutations of $[n]$. 

\begin{obs}
If $\pi \in \S_n$ then the restriction of $\pi$ to the set
$\Ltr(\pi)$ is monotone increasing. If, moreover, $\pi \in
\S_n(321)$ then the restriction of $\pi$ to the complementary set
$[n] \setminus \Ltr(\pi)$ is also monotone increasing.
\end{obs}

\begin{obs}\label{obs2}
If $\pi \in \S_n(321)$ then the set $\Ltr(\pi)$ uniquely
determines the set $\Des(\pi)$. Explicitly, for any $1 \le i \le
n-1$,
\[
i \in \Des(\pi) \iff i \in \Ltr(\pi) \text{ and } i+1 \not\in
\Ltr(\pi).
\]
\end{obs}

For a permutation $\pi\in S_n$ let
\[
\ldes(\pi):=\max\{i \,:\, i \in \Des(\pi)\},
\]
be its {\em last descent}, with $\ldes(\pi) := 0$ if $\Des(\pi) =
\varnothing$ (i.e., if $\pi$ is the identity permutation).


For a skew shape $\lambda/\mu$, let $height(\lambda/\mu)$ be the number of rows in $\lambda/\mu$ and let $\SYT(\lambda/\mu)$ be the set
of standard Young tableaux of shape $\lambda/\mu$. We use the
English convention, according to which row indices increase from
top to bottom
(see, e.g., \cite[Ch.\ 2.5]{Sagan}).
The {\em descent set} of a standard Young tableau $T$
is
\[
\Des(T):=\{i \,:\, i+1 \text{ appears in a lower row of } T \text{
than } i\}.
\]
Its {\em last descent} is
\[
\ldes(T):=\max\{i \,:\, i \in \Des(T)\},
\]
with $\ldes(T) := 0$ if $\Des(T) = \varnothing$.





We shall make use of the Robinson-Schensted-Knuth (RSK)
correspondence which maps each permutation $\pi \in \S_n$ to a
pair $(P_{\pi}, Q_{\pi})$ of standard Young tableaux of the same
shape $\lambda \vdash n$. A detailed description can be found, for
example, in  \cite[Ch.\ 3.1]{Sagan} or in \cite[Ch.\ 7.11]{St2}. A
fundamental property of the RSK correspondence is:

\begin{fact}\label{fact:RSK_DES}
For each $\pi\in \S_n$, $\Des(P_{\pi}) = \Des(\pi^{-1})$ and
$\Des(Q_{\pi}) = \Des(\pi)$.
\end{fact}

\subsection{The $k$-fold Catalan number}\label{sec:prel_Catalan}

Recall the $n$-th Catalan number, defined by
\[
C_n := \frac{1}{n+1} {2n \choose n} = {2n \choose n} - {2n \choose
n+1} \qquad (n \ge 0),
\]
with generating function
\[
c(x) := \sum_{n=0}^{\infty} C_n x^n = \frac{1-\sqrt{1-4x}}{2x}.
\]


For each $0 \le k \le n$, the {\em $n$-th $k$-fold Catalan number}
$C_{n,k}$ is the coefficient of $x^n$ in $(xc(x))^k$. These
numbers are also called {\em ballot numbers}, and form the {\em
Catalan triangle}~\cite[A009766]{OEIS}. As proved by Catalan
himself~\cite{C}, they are given explicitly by
\[
C_{n,k} = \frac{k}{2n-k} {2n-k \choose n} = {2n-k-1 \choose n-1} -
{2n-k-1 \choose n} \qquad (1 \le k \le n)
\]
and $C_{n,0} = \delta_{n,0}$ $(n \ge 0)$; in particular, $C_{n,1}
= C_{n-1}$ for $n \ge 1$.

Among the many interpretations of $C_{n,k}$ one can mention the
number of lattice paths from $(k,1)$ to $(n,n)$, consisting of
steps $(1,0)$ and $(0,1)$, which never go strictly above the line
$y=x$; see, e.g., \cite[Cor.\ 16]{T} which uses a slightly
different indexing.

The following proposition, reformulating results presented in
\cite{CGG, T}, relates the $k$-fold Catalan numbers to
$321$-avoiding permutations and to standard Young tableaux.


\begin{proposition}\label{prop1} {\rm (\cite{CGG, T})}
For positive integers $1 \le k \le n$,
\[
|\{\pi \in \S_n(321) \,:\, \ldes(\pi^{-1})=n-k\}| = 
|SYT(n-1,n-k)| = C_{n,k}.
\]
\end{proposition}




\subsection{Quasi-symmetric functions}\label{sec:prel_quasi}

\ytableausetup{centertableaux}

Schur functions $\{s_{\lambda} \,:\,
\lambda \vdash n\}$, indexed by partitions of $n$, 
form a distinguished basis for the vector space $\Lambda^n$ of symmetric functions which are homogeneous of degree $n$; see, e.g., \cite[Corollary 7.10.6]{St2}. 
Recall that a symmetric function in $\Lambda^n$ is {\em Schur-positive} if 
all the coefficients in its expansion in this basis of Schur functions are nonnegative.

\begin{defn}{\rm \cite[7.19]{St2}}
A {\em quasi-symmetric function} (with rational coefficients) in the variables $x = (x_1, x_2,\ldots)$ is a formal power series $f(x) \in \mathbb{Q}[[x]]$, of bounded degree, such that
for any nonnegative integer exponents $a_1, \ldots, a_k$ and any two increasing lists of indices $i_1 < \ldots < i_k$ and $j_1 < \ldots < j_k$
\[
[x_{i_1}^{a_1} \cdots x_{i_k}^{a_k}]f =[x_{j_1}^{a_1}\cdots x_{j_k}^{a_k}]f.
\]
\end{defn}
Clearly, every symmetric function is quasi-symmetric, but not conversely, as the series $\sum_{i<j} x_i^2 x_j$ shows. 

For each subset $D \subseteq [n-1]$ define the {\em fundamental quasi-symmetric function}
\[
\F_{n,D}(\x) := \sum\limits_{i_1\le i_2 \le \ldots \le i_n \atop
{i_j < i_{j+1} \text{ if } j \in D}} x_{i_1} x_{i_2} \cdots
x_{i_n}.
\]

Let $\BBB$ be a (multi)set of combinatorial objects, equipped with
a {\em descent map} $\Des: \BBB \to 2^{[n-1]}$ which associates to
each element $b\in \BBB$ a set $\Des(b) \subseteq [n-1]$.
Define the quasi-symmetric function
\[
\Q(\BBB) := \sum\limits_{b\in \BBB} m(b,\BBB) \F_{n,\Des(b)},
\]
where $m(b,\BBB)$ is the multiplicity of the element $b$ in
$\BBB$. With some abuse of terminology, we say that $\BBB$ is
Schur-positive when $\Q(\BBB)$ is.

\medskip

The following key theorem is due to Gessel.

\begin{proposition}\label{G1}
{\rm \cite[Theorem 7.19.7]{St2}}
For every shape $\lambda \vdash n$,
\[
\Q({\SYT(\lambda)})=s_{\lambda}.
\]
\end{proposition}

Recall the notation $P_\pi$ from \cref{subsec:stat}. For
every standard Young tableau $T$ of size $n$, the set
\[
{\mathcal C}_T := \{\pi \in \S_n \,:\, P_\pi = T\}
\]
is the {\em Knuth class} corresponding to $T$.
\cref{fact:RSK_DES} and \cref{G1} imply the
following well-known result.

\begin{proposition}\label{Knuth_positive}
Knuth classes are Schur-positive.
\end{proposition}

The following lemma will be used in \cref{sec:Schur}.

\begin{lemma}\label{prop:first-last}
{\rm \cite[Lemma 8.1]{ER}}
For every Schur-positive set $A \subseteq \S_n$, the (set) statistics $\Des$ and $n-\Des := \{n-i \,|\, i \in \Des \}$ are
equi-distributed over $A$.
\end{lemma}



\section{The block number of a permutation}\label{sec:block_number}


\subsection{Definitions}\label{sec:block}

Direct sums and block decomposition of permutations appear naturally in the study of pattern-avoiding classes~\cite{Albert-Atkinson05, AAV}.


Let $\pi \in \S_m$ and $\sigma \in \S_n$. The {\em direct sum} of
$\pi$ and $\sigma$ is the permutation $\pi \oplus \sigma \in
\S_{m+n}$ defined by
\[
\pi \oplus \sigma :=
\begin{cases}
\pi(i), & \text{if } i \leq m;  \\
\sigma(i-m) + m,  & \text{otherwise.}
\end{cases}
\]

For example, if $\pi = 312$ and $\sigma = 2413$ then $\pi \oplus
\sigma = 3125746$; see \cref{fig:sum}.

%
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.6]{sum.PNG}
\caption{The permutation $312\oplus 2413=3125746$ 
}\label{fig:sum}
\end{center}
\end{figure}

A nonempty permutation which is not the direct sum of two nonempty
permutations is called {\em $\oplus$-irreducible}. Each
permutation $\pi$ can be written uniquely as a direct sum of
$\oplus$-irreducible ones, called the {\em blocks} of $\pi$; their
number, denoted by $\bl(\pi)$, is the {\em block number} of $\pi$.

\begin{exa}
$\bl(45321)=1$, $\bl(31254)=2$, and $\bl(1234)=4$.
\end{exa}



\begin{obs}\label{obs:bl}
The block number of a permutation $\pi\in \S_n$ is
\[
\bl(\pi)= 1 + |\{1 \le i \le n-1 \,:\, \max(\pi(1), \ldots,
\pi(i)) < \min(\pi(i+1), \ldots, \pi(n))\}|.
\]
\end{obs}


The following equivalent definition was proposed by Michael Joseph and Tom Roby~\cite{personal}.
\begin{obs}
\[
\bl(\pi) = |\{1 \le i \le n \,:\, (\forall j \le i)\, \pi(j) \le i
\}|.
\]
\end{obs}



\subsection{Counting 321-avoiding permutations by block number}\label{sec:count}

Recall from \cref{sec:prel_Catalan} the Catalan
generating function
\[
c(x) := \sum\limits_{n=0}^{\infty}{C_n x^n}.
\]

One can prove without difficulty (see~\cite{ABagR})
\begin{proposition}\label{prop:Bl_Catalan}
For any fixed positive integer $k$, the ordinary generating
function for the number of $321$-avoiding permutations in $\S_n$
$(n \ge k)$ with exactly $k$ blocks is $(xc(x))^k$.
\end{proposition}




Combining \cref{prop:Bl_Catalan} with
\cref{prop1} we deduce

\begin{corollary}\label{t:cardinalities}
For any integers $1\le k\le n$,
\begin{eqnarray*}
|\{\pi \in \S_n(321) \,:\, \bl(\pi) = k\}|
&=& \{\pi \in \S_n(321) \,:\, \ldes(\pi^{-1}) = n-k\}| \\
&=& |\SYT(n-1,n-k)|.
\end{eqnarray*}
\end{corollary}

\cref{t:cardinalities} is refined in this paper; see
\cref{main1_introduction} above and 
\cref{t:des_equid} below.


\section{Equi-distribution}\label{sec:equidistribution}

\begin{defn}
For $1 \le k \le n$ denote
\[
Bl_{n,k}:=\{\pi\in \S_n(321):\ \bl(\pi) = k\}
\]
and
\[
L_{n,k} = \{\pi \in \S_n(321) :\ \ldes(\pi^{-1})=k\}. \]
\end{defn}

\cref{main1_introduction} is proved via a
left-to-right-maxima-preserving bijection from $Bl_{n,k}$ to
$L_{n,n-k}$.


\begin{defn}\label{def:recursion}
Define maps $f_n: \S_n(321) \to \S_n(321)$, recursively, for all
$n \ge 1$. For $n = 1$ the definition is obvious, since
$\S_1(321)$ consists of a unique permutation. For $\pi \in
\S_n(321)$, $n \ge 2$, the recursive definition of $f_n(\pi)$
depends on $k := \bl(\pi)$ and on the locations of the letters
$n-1$ and $n$ in $\pi$.
Distinguish the following three cases:

\begin{description}
\item[{\bf Case A:}]
$\pi^{-1}(n)=n$,\ i.e., $n$ is in the last position.\\
Then: delete $n$, apply $f_{n-1}$, and insert $n$ at the last
position.

\item[{\bf Case B:}]
$\pi^{-1}(n-1)< \pi^{-1}(n) < n$, i.e., $n$ is to the right of $n-1$ but not in the last position.\\
Then: delete $n$, apply $f_{n-1}$,  insert $n$ at the same
position as in $\pi$, and multiply on the left by the
transposition $(n-k-1,n-k)$.

\item[{\bf Case C:}] $\pi^{-1}(n) < \pi^{-1}(n-1)$, i.e.,
$n-1$ is to the right of $n$ (and must be the last letter, since $\pi$ is $321$-avoiding).\\
Then: let $\pi' := (n-1,n)\pi$, define $f_n(\pi')$ according to
case A above, and multiply it on the left by the cycle
$(n-k,n-k+1, ...,n)$.
\end{description}
\end{defn}

\begin{remark}\label{rem:sequence}
This recursive definition yields a sequence of permutations
$(\pi_n,\pi_{n-1},\dots,\pi_1)$, starting with $\pi_n = \pi$. For
each $2 \le i \le n$, $\pi_{i-1} \in \S_{i-1}$ is obtained from
$\pi_{i} \in \S_i$ by deleting $i$ from $\pi_{i}$ (in cases A and
B) or by deleting $i$ from $(i-1,i)\pi_{i}$ (in case C). To
recover $f_i(\pi_{i})$ from $f_{i-1}(\pi_{i-1})$, the letter $i$
is inserted exactly where it was deleted (for example --- in the
last position, in cases A and C), and then the permutation is
multiplied, on the left, by a suitable cycle.
\end{remark}

\begin{example}\label{main example}
Let $\pi=31254786 \in \S_8$, so that $\bl(\pi)=3$ and
$\Ltr(\pi)=\{1,4,6,7\}$. The recursive process is illustrated by
the following diagram, where the arrow $\pi_{i} \to \pi_{i-1}$ is
decorated by the case and by the corresponding cycle.
%
\begin{eqnarray*}
\pi=\pi_8=31254786 &\xrightarrow[(45)]{B}& \pi_7=3125476 \xrightarrow[(4567)]{C} \pi_6=312546 \\
&\xrightarrow[\quad]{A}& \pi_5=31254 \xrightarrow[(345)]{C} \pi_4=3124\xrightarrow[\quad]{A} \pi_3=312 \\
&\xrightarrow[(23)]{C}& \pi_2=21\xrightarrow[(12)]{C} \pi_1=1 .
\end{eqnarray*}


\begin{eqnarray*}
f_1(\pi_1) = 1 &\xrightarrow{(12)}& f_2(\pi_2)=21 \xrightarrow{(23)} f_3(\pi_3)=312 \xrightarrow{\quad} f_4(\pi_4)=3124 \\
&\xrightarrow{(345)}& f_5(\pi_5)=41253
\xrightarrow{\quad} f_6(\pi_6)=412536 \\
&\xrightarrow{(4567)}& f_7(\pi_7)=5126374 \xrightarrow{(45)}
f_8(\pi)=f_8(\pi_8)=41263785.
\end{eqnarray*}


Note that here $\ldes(f_8(\pi)^{-1}) = 5 = 8-\bl(\pi)$ and
$\Ltr(f_8(\pi)) = \{1,4,6,7\} = \Ltr(\pi)$.
\end{example}

Our main claim is

\begin{theorem}\label{t:bijection}
For each $1 \le k \le n$, the map $f_n$ defined above is a
left-to-right-maxima-preser\-ving bijection from $Bl_{n,k}$ onto
$L_{n,n-k}$.
\end{theorem}

The (quite technical) proof of \cref{t:bijection} is
given in the full paper version~\cite{ABagR}.

\bigskip

\cref{main1_introduction} follows from \cref{t:bijection}, and implies in turn

\begin{corollary}\label{t:des_equid}
For every positive integer $n$,
\[
\sum_{\pi \in \S_n(321)} {\bf x}^{\Des(\pi)} t^{\pi^{-1}(n)}
q^{\bl(\pi)} = \sum_{\pi \in \S_n(321)} {\bf x}^{\Des(\pi)}
t^{\pi^{-1}(n)}  q^{n-\ldes(\pi^{-1})}.
\]
\end{corollary}


\begin{proof}
By \cref{obs2}, the set $\Ltr(\pi)$ determines
$\Des(\pi)$. In addition, $\pi^{-1}(n)$ is the maximal element of
$\Ltr(\pi)$.
\end{proof}


\section{Proof of \cref{conj1}}\label{sec:Schur}

Setting $t=1$ in \cref{t:des_equid} gives
\[
\sum_{\pi \in \S_n(321)} {\bf x}^{\Des(\pi)} q^{\bl(\pi)} =
\sum_{\pi \in \S_n(321)} {\bf x}^{\Des(\pi)} q^{n
-\ldes(\pi^{-1})},
\]
and comparing the coefficients of $q^k$ on both sides gives
\[
\Q(Bl_{n,k})=\Q(L_{n,n-k}) \qquad (1 \le k \le n).
\]
It therefore suffices to prove the claim for $L_{n,n-k}$ instead
of $Bl_{n,k}$.

Note that a permutation $\pi$ is $321$-avoiding if and only if
$height(P_\pi) < 3$, in the terminology of
\cref{subsec:stat}. The set
\begin{eqnarray*}
L_{n,n-k} &=& \{\pi \in \S_n(321) \,:\, \ldes(\pi^{-1}) = n-k\} \\
&=& \{\pi \in \S_n \,:\, height(P_\pi) < 3 \text{ and }
\ldes(P_\pi) = n-k\}
\end{eqnarray*}
is therefore a disjoint union of Knuth classes and thus, 
by \cref{Knuth_positive}, Schur-positive.
By
the above description of $L_{n,n-k}$, \cref{fact:RSK_DES} and
\cref{G1},
\begin{eqnarray*}
\Q(L_{n,n-k}) &=& \sum_{\pi \in
L_{n,n-k}}{\mathcal{F}_{n,\Des(\pi)}}
= \sum_{\substack{\lambda \vdash n \\ \ell(\lambda) < 3}} \,\sum_{\substack{P \in \SYT(\lambda) \\ \ldes(P) = n-k}} \sum_{Q \in \SYT(\lambda)}{\mathcal{F}_{n,\Des(Q)}} \\
&=& \sum_{\substack{\lambda \vdash n \\ \ell(\lambda) < 3}} |\{P
\in \SYT(\lambda) \,:\, \ldes(P) = n-k\}| \, s_{\lambda}.
\end{eqnarray*}
We conclude that, for every $\lambda \vdash n$,
\begin{equation}\label{eq_coeff}
\langle \Q(Bl_{n,k}), s_\lambda \rangle=
\langle \Q(L_{n,n-k}), s_\lambda \rangle = \begin{cases}
|\{P\in \SYT(\lambda) \,:\, \ldes(P) = n-k\}|, & \text{if } \ell(\lambda) < 3;\\
0, & \text{otherwise}.
\end{cases}
\end{equation}

For $k = n$ we have $\ldes(P) = 0$ only for the unique tableau of shape $\lambda = (n)$, so that
\[
\langle \Q(L_{n,0}), s_\lambda \rangle 
= \delta_{\lambda, (n)} 
\]
and therefore
\[
\Q(L_{n,0}) = s_{(n)}
\]
as claimed. 

Assume now that $1 \le k \le n-1$,
so that $n \le (n-1) + (n-k)$.
By the Branching Rule~
\cite[Theorem 2.8.3]{Sagan},
if
$\lambda \vdash n$ is not contained in $(n-1,n-k)$ then
\[
\langle \chi^{(n-1,n-k)} \downarrow_{\S_n}^{\S_{2n-k-1}},
\chi^\lambda \rangle = 0,
\]
and also 
\[
\langle \Q(L_{n,n-k}), s_\lambda \rangle = 0
\]
since a standard tableau $P\in \SYT(\lambda)$ (with $\ell(\lambda) < 3$, namely $\lambda = (n-m,m)$ with either $m = 0$ or $m > n-k$)  cannot have $\ldes(P) = n-k$.

If $\lambda = (n-m,m)$ with $1 \le m \le n-k$ then
\[
\langle \chi^{(n-1,n-k)} \downarrow_{\S_n}^{\S_{2n-k-1}},
\chi^{(n-m,m)}\rangle = |\SYT((n-1,n-k)/(n-m,m))|.
\]
Rotating the shape by $180^\circ$ within a $2 \times n$ box, the right side
is seen to be equal to
\[
|\SYT((n-m,m)/(k,1))|.
\]
This, in turn, is equal to the number of SYT of shape $(n-m,m)$
with the smallest $k+1$ entries filling a $(k,1)$ shape in some
specific order, say the one with $1, \ldots, k$ in the first row
and $k+1$ in the second. These are exactly the SYT of shape
$(n-m,m)$ with first descent equal to $k$. By
\cref{prop:first-last}, this number is equal to the number of
SYT of shape $(n-m,m)$ with last descent equal to $n-k$, namely to
\[
|\{P \in \SYT(\lambda) \,:\, \ldes(P) = n-k\}| = \langle
\Q(L_{n,n-k}), s_\lambda \rangle.
\]
Thus
\[
\Q(L_{n,n-k}) = \ch(\chi^{(n-1,n-k)}
\downarrow_{\S_n}^{\S_{2n-k-1}}),
\]
as claimed.
\qed



\section{Final remarks}\label{sec:final_remarks}


\subsection{Hilbert series}

Let $P_n/I_n$ be the quotient of the polynomial ring $P_n =\mathbb{Q}[x_1,\dots,x_n]$ by the ideal generated by quasi-symmetric functions without constant term. 
This algebra was studied by Aval, Bergeron and Bergeron~\cite{ABB}, who determined its Hilbert series with respect to the grading by total degree in terms of statistics on Dyck paths. 
An alternative description follows from \cref{t:des_equid}.

\begin{proposition}
The Hilbert series of the quotient $P_n/I_n$, graded by total degree, is equal to
\[
\sum_{\pi \in \S_n(321)} {q^{n-\bl(\pi)}}.
\]
\end{proposition}

It is now desired to find two different bases for the graded ring
$P_n/I_n$, both indexed by $321$-avoiding
permutations, with total degree equal to the block-number and to
the last descent, respectively. Determining a nicely behaved linear
action of the symmetric group (or of the Temperley-Lieb algebra)
on these bases may provide a representation theoretic proof of
\cref{t:des_equid}.


\subsection{Schur-positive pattern-statistic pairs}


Sagan and Woo~\cite{Sagan_talk} raised the problem of finding Schur-positive
pattern-avoiding sets.
A natural goal is to look, further, for Schur-positive statistics on
pattern-avoiding sets.

\begin{defn}
Let $\stat:\S_n \longrightarrow \bbn$ be a permutation
statistic, and let $\varnothing \ne \Pi\subseteq \S_m$ be a nonempty set
of patterns. The {\em pattern-statistic pair} $(\Pi,\stat)$ is
{\em Schur-positive} if
\[
\Q(\{\pi \in \S_n(\Pi) \,:\, \stat(\pi) = k\})
\]
is Schur-positive for all integers $n \ge 1$ and $k \ge 0$.
\end{defn}

By \cref{Knuth_positive}, sets of permutations which
are closed under Knuth relations are Schur-positive.
It follows that
if $\S_n(\Pi)$ is closed under Knuth relations for every $n$, 
and the statistic $\stat$ is also invariant under these relations, then
$(\Pi,\stat)$ is a Schur-positive pair. For example, letting
$\ides(\pi):=|\Des(\pi^{-1})|$ 
and $e_m\in \S_m$ be the identity permutation, the pair $(\{e_m\},
\ides)$ is Schur-positive. For similar reasons, the pair
$(\{132,312\}, \imaj)$ is Schur-positive, where $\imaj(\pi)$ is the major index of $\pi^{-1}$.


An example of a different type was given in this paper:
By \cref{conj1}, $(\{321\}, \bl)$ is a Schur-positive pair. Note that the block number is not invariant under Knuth relations.

\begin{problem}
Find other Schur-positive pattern-statistic pairs, which are not
invariant under Knuth relations.
\end{problem}

\printbibliography


\end{document}
